// 994. 腐烂的橘子/队列BFS
// https://leetcode.cn/problems/rotting-oranges/
// std::set自定义结构体需要重写operator<
//在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
//值 0 代表空单元格；值 1 代表新鲜橘子；值 2 代表腐烂的橘子。
//每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
//返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。
// 如果不可能，返回-1。
// 输入：grid = [[2,1,1],[0,1,1],[1,0,1]] 
// 输出：-1 解释：左下角的橘子（第2行，第0列）永远不会腐烂，
// 因为腐烂只会发生在 4 个正向上。

#include <bits/stdc++.h>
using namespace std;
#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#else
#define PF(...)
#endif
class Solution {
  struct Coordinate {
    int x = 0, y = 0;
    bool operator<(const Coordinate& oth) const {
      if (x == oth.x) return y < oth.y;
      return x < oth.x;
    }
  };

 public:
  int orangesRotting(vector<vector<int>>& grid) {
    vector<Coordinate> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    queue<tuple<int, int, int>> quNode;  // i,j,dis
    set<Coordinate> stVisited;
    int n = grid.size();           // rows
    int m = grid[0].size();        // cols
    int nFreshCnt = 0;             // fresh orange Count
    for (int i = 0; i < n; i++) {  // rows
      for (int j = 0; j < m; j++) {
        if (grid[i][j] == 2) {
          quNode.push({i, j, 0});
          stVisited.insert({i, j});
        } else if (grid[i][j] == 1) {
          nFreshCnt++;
        }
      }
    }
    int nFindCount = 0;  // find fresh orange Count
    int nCostTime = 0;
    while (!quNode.empty()) {
      auto [i, j, dis] = quNode.front();
      quNode.pop();
      for (auto [dx, dy] : dirs) {
        int x = i + dx, y = j + dy;
        if (x < 0 || x >= n || y < 0 || y >= m) {
          continue;
        }
        if (stVisited.count({x, y}) > 0) {
          continue;
        }
        if (grid[x][y] == 0) {
          continue;
        }
        if (grid[x][y] == 1) {
          nFindCount++;
        }
        if (nFindCount == nFreshCnt) {
          nCostTime = dis + 1;
          goto END_;
        }
        quNode.push({x, y, dis + 1});
        stVisited.insert({x, y});
      }
    }
  END_:
    int remaining = nCostTime;
    if (nFindCount < nFreshCnt) {
      remaining = -1;
    }
    return remaining;
  }
};
int main() {
  vector<vector<int>> grid;
  grid.push_back({2, 1, 1});
  grid.push_back({1, 1, 0});
  grid.push_back({0, 1, 1});
  Solution sol;
  int n = sol.orangesRotting(grid);
  cout << n << endl;
  return 0;
}